package Hot_100;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

public class T39_combinationSum {
    @Test
    public void test() {
        int[] candaidates = {2,3,6,7};
        List<List<Integer>> ans = combinationSum(candaidates, 7);
        System.out.println(ans);
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> res = new ArrayList<>();
        DFS(candidates, target, ans,  res,0);
        return ans;
    }

//    这题进行dfs最大的问题就是终止条件怎么写，不然会出现栈溢出的情况
    void DFS(int[] candidates, int target,  List<List<Integer>>ans, List<Integer>res,int index) {
        if (index == candidates.length) {
            return;
        }
        if (target==0) {
            ans.add(new ArrayList<>(res));
            return;
        }
        //1.  不选(不选需要移动指针，不然算重复了，递归下去和递归前是一样的，没有意义)
        DFS(candidates, target, ans, res,index + 1);
        // 如果是选了，可以移动指针，也可以不移动，下次还可以继续选该数
        // （但是选了之后移动的情况属于选了不移动的一个子递归，如果两个都写就会计算出重复解了）
        if (target - candidates[index] >= 0) {
            res.add(candidates[index]);
            //2.  选但不移动指针
            DFS(candidates, target-candidates[index], ans, res, index);
            res.remove(res.size() - 1);
            //之所以不适用 res.remove(candidates[index])的原因，是因为res里面可能会存在重复的元素，remove(Object obj)是按照从左到右，
            // 删除的元素不一定是刚加入的元素
        }
    }

    /**
     *  此dfs求解过程中不会出现重复解的情况，比如 [2 2 3] 和 [3 3 2] ，因为它是按index递增的
     * @param candidates
     * @param target
     * @param ans
     * @param combine
     * @param idx 指向candidates的索引
     */
    public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> combine, int idx) {
        if (idx == candidates.length) { //idx一直为0只有一种情况，那就是每次递归都加上 下标为0对应的元素，那最终会在target - candidates[idx] < 0的条件下结束, 不会出现死递归的情况
            return;
        }
        if (target == 0) {
            ans.add(new ArrayList<Integer>(combine)); //最后加入的时候要用new，否则操作的都是同一个combine，在其他递归中可能被修改掉
            return;
        }
        // 直接跳过
        dfs(candidates, target, ans, combine, idx + 1);

        // 选择当前数
        if (target - candidates[idx] >= 0) {
            combine.add(candidates[idx]);
            dfs(candidates, target - candidates[idx], ans, combine, idx);
            combine.remove(combine.size() - 1);
            //回溯的原因:选了当前数的下一个分支不一定正确，可能在下一轮递归被返回，那么返回上一层递归的时候就应该剔除该数，以恢复原来的状态;
        }
    }

    public List<List<Integer>> combinationSum_2(int[] candidates, int target) {
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> combine = new ArrayList<>();
        dfs(candidates, target, ans, combine, 0);
        return ans;
    }

    @Test
    public void test2() {
        int[] candaidates = {2,3,6,7};
        List<List<Integer>> ans = combinationSum_2(candaidates, 7);
        System.out.println(ans);
    }
}